#include <stdio.h>
#include <malloc.h>
//实现二叉搜索树 binary search tree BST
//特点：左子树比根结点小 右子树比根结点大

//1.定义数据结构
typedef int  ElementType;
typedef struct node *BSTnode;
struct node{
    //1.数据项
    ElementType data;
    //2.地址项 存两个指针，分别指向左右子结点
    struct node *left;
    struct node *right;
};

//2.1 插入 insert
//   应用递归思想
/*   步骤：（1）待插入的值与当前的结点进行比较
 *        （2）如果待插入值大，则该值插入到右子树
 *        （3）如果待插入值小，则该值插入到左子树
 *
 * 函数名：createBST()
 * 输入：树的根，待插入的值
 * 输出：返回创建好的结点
 *
 *
 * */
BSTnode createBST(BSTnode root,ElementType value){
    //1.如果树为空
    if(root == NULL){
        //1.1分配空间
        root=malloc(sizeof(struct node));
        //1.2 赋值
        root->data=value;
        root->left=NULL;
        root->right=NULL;
        return root;
    }
    //2.1如果value大于当前树的根结点的值，则该值需要插入到右子树里
    if(value>root->data)
        root->right = createBST(root->right,value);
    else if(value<root->data)
        root->left = createBST(root->left,value);
    return root;
}

//找最大值
/*
 * findmax(){
 *
 * while(){
 * node =node.right;
 * }
 *  //return node;
 *  return node.data;
 * }
 * */
/*
 * 函数名：findMax()
 * 输入：树
 * 输出：返回包含最大值的结点
 * */
BSTnode findMax(BSTnode bst){
    //树为空
    if(bst==NULL)
        return NULL;
    //查找最大值得过程就是指针不断地向右，直到找到最右端的结点
    BSTnode node =bst;
    while (node->right!=NULL){
        node = node->right;
    }
    return node;
}
BSTnode findMin(BSTnode bst){
    //树为空
    if(bst==NULL)
        return NULL;
    //查找最大值得过程就是指针不断地向右，直到找到最右端的结点
    BSTnode node =bst;
    while (node->left!=NULL){
        node = node->left;
    }
    return node;
}

//找包含给定值的结点
/*
 * 方法：对比
 * 传入的值：value
 * 当前根节点：node
 * value >node.data  在右子树里
 * value < node.data 在左子树里
 * value == node.data 找到
 * node==NULL 未找到
 * */
/*
 * 函数名：findNode()
 * 输入：树，数据值
 * 输出：找到  包含该值的结点  没找到 返回NULL
 *
 * */
BSTnode findNode(BSTnode root,ElementType value){
    if(root ==NULL)
        return NULL;
    //查找过程
    if(value>root->data){
       return findNode(root->right,value);
    }
    if(value <root->data)
       return findNode(root->left,value);
    if(value ==root->data)
        return root;

}
/*
 * 迭代的伪代码
 * BST tmp =root;
 * while(tmp!=NULL){
 *   if value >   tmp=tmp.right
 *   if value <   tmp = tmp.left;
 *   if value ==  tmp.data return tmp
 * }
 * return tmp;
 *
 *
 * */
int main() {
    BSTnode root =NULL;
    root = createBST(root,2);
    root = createBST(root,1);
    root = createBST(root,3);
    root = createBST(root,23);
   BSTnode maxNode = findMin(root);
    printf("树的最大值是%d\n",maxNode->data);
    BSTnode tmp = findNode(root,43);
    if(tmp)
        printf("结点存在\n");
    else
        printf("结点不存在\n");

    //printf("Hello, World!\n");
    return 0;
}
